package com.sicheng.蓝桥.练习题.基础图论.迷宫系列;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/13 17:29
 */
public class 样本收集 {
    //问题描述：机器人Rob在一个有n*n个方格的方形区域F中收集样本。
    // （i,j）方格中样本的价值为v(i,j)，如图所示。Rob从方形区域F的左上角A点出发，
    // 向下或向右行走，直到右下角的B点，在走过的路上，收集方格中的样本。Rob从A点到B点共走两次，
    // 试找出Rob的2条行走路径，使其取得的样本总价值最大。

    /**
     * 由文件input.txt给出输入数据。第一行有1个正整数n，表示方形区域F有n*n个方格。
     * 接下来每行有3个整数，前2个数表示方格位置，第3个数为该位置样本价值。最后一行是3个0。
     * 结果输出：将计算的最大样本总价值输出到文件output.txt。
     * 输入文件示例
     * input.txt            output.txt
     * 8                       67
     * 2 3 13
     * 2 6 6
     * 3 5 7
     * 4 4 14
     * 5 2 21
     * 5 6 4
     * 6 3 15
     * 7 2 14
     * 0 0 0
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] v = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int value = scanner.nextInt();
            if (x == 0 && y == 0 && value == 0)
                break;
            v[x][y] = value;
        }

        bfs(n, v);
    }

    static int[][] d = {{0, 1}, {1, 0}};
    static int count = 2;
    static int res = 0;

    private static void bfs(int n, int[][] v) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((e1, e2) -> e2[2] - e1[2]);

        int[] p0 = {1, 1, v[1][1]};
        heap.offer(p0);
        v[1][1] = 0;
        while (!heap.isEmpty()) {

            int[] p = heap.poll();
            for (int[] ints : d) {
                int x = p[0] + ints[0];
                int y = p[1] + ints[1];
                int value = p[2];
                if (x >= 1 && x <= n && y >= 1 && y <= n && v[x][y] != -count) {
                    int[] e = {x, y, value + v[x][y]};
                    heap.offer(e);
                    v[x][y] = -count;
                    if (x == n && y == n) {
                        count--;
                        res += e[2];
                        if (count == 0)
                            return;
                    }
                }
            }

        }
    }
}
